package one2Ten;

import java.util.Arrays;

/**
 * 根据前序和中序，重组二叉树
 * Created by Wongy on 2018/3/9.
 */
//todo 自己做后序和中序重组二叉树
public class Six6 {


    private static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null) {
            return null;
        }
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        if (pre.length != in.length) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        for (int i = 0; i < pre.length; i++) {
            if (pre[0] == in[i]) {
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
            }
        }
        return root;
    }

    private static TreeNode reConstructBinaryTreeDesc(int[] suf, int[] in) {
        if (suf == null || in == null) {
            return null;
        }
        if (suf.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(suf[suf.length - 1]);
        for (int i = 0; i < in.length; i++) {
            if (suf[suf.length - 1] == in[i]) {
                System.out.println("i = " + i);
                printArray(Arrays.copyOfRange(suf, 0, i));
                printArray(Arrays.copyOfRange(in, 0, i));
                System.out.println("----------");
                root.left = reConstructBinaryTreeDesc(Arrays.copyOfRange(suf, 0, i), Arrays.copyOfRange(in, 0, i));
                root.right = reConstructBinaryTreeDesc(Arrays.copyOfRange(suf, i, suf.length - 1), Arrays.copyOfRange(in, i + 1, in.length));
            }
        }
        return root;
    }

    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        int[] suf = {7, 4, 2, 5, 8, 6, 3, 1};
//        TreeNode treeNode = reConstructBinaryTree(pre, in);
//        preOrder(treeNode);
        TreeNode treeNode1 = reConstructBinaryTreeDesc(suf, in);
        preOrder(treeNode1);
    }

    private static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        preOrder(root.left);
        preOrder(root.right);
        System.out.print(root.val + " , ");
    }

    private static void printArray(int[] arrayList) {
        for (Object o : arrayList) {
            System.out.print(o + " ");
        }
        System.out.println();
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
